Video special effect systems for spatially transforming two-dimensional real-time or "live" television video images are well-known. These systems are capable of generating two-dimensional video images which can be displayed and transformed in a variety of ways including rotation, translation and perspective manipulation.
A typical television special effects processor operates by first digitizing a normal analog television signal to generate a plurality of digital pixels which represent the digitized picture. The pixels for each television frame are then stored as "source" pixels in a field memory. The source pixels stored in the memory are sequentially used to generate output pixels in each scan line in the output picture. More specifically, a control circuit which has been programmed with the desired mathematical image transformation equations repetitively fetches source pixels from the memory. The source pixels are fetched from memory locations which will generate the next pixel on the output scan line. Using the image transformation equations, a transformation circuit computes the pixel value of the next pixel in order to generate an output transformed video signal. With specialized hardware, the entire process of storing and computing the transformed video information can be repeated at a rate sufficient so that the output video image changes at a television processing rate and produces "live" transformed television images. An example of such a system is shown in U.S. Pat. No. 4,631,750 entitled "Method and System for Spatially Transforming Images" issued on Dec. 23, 1986.
While the aforementioned two-dimensional system is capable of generating a variety of digital special effects at a real-time video rate and of simulating certain three-dimensional effects, it does not have true three-dimensional capability. For example, it is not possible with such a system to rotate a three-dimensional object with real-time video displayed as the object rotates.
True three-dimensional objects and effects have been achieved in computer graphics systems. Although there are many methods of representing three-dimensional shapes that are well-known in the computer graphics area, a typical method of constructing a 3D shape is to approximate the shape by using geometrical surfaces. From the surfaces, mathematical equations are derived which represent the overall shape. These equations can then be transformed by transformation matrices which control how each surface of the shape moves when the constructed object is rotated, translated or scaled.
Generally, the prior art area shape construction or modeling is quite broad. However, two commonly used methods to represent three-dimensional surfaces are polygon meshes and parametric bicubic patches. A polygon mesh is generally considered to be a set of connected polygonal planar surfaces. Such meshes can be used to represent flat or curved surfaces. However, with curved surfaces, the representation is only approximate. Parametric bicubic patches are more suited for curved surfaces and can represent points on a curved surface by using three equations, one for each of the x, y and z axis directions. Each equation has two variables in terms for all powers of the parameters up to their cubic value. The boundaries of each patch are, therefore, parametric cubic curves. Many fewer bicubic patches than polygonal patches are needed to represent a curved surface to a given accuracy, but the mathematical algorithms required to work with the bicubic mathematics are considerably more complex than those necessary to work with planar polygons.
With either polygons or bicubic patches, a 3D shape is constructed by modeling the outer shape surface by means of plurality of polygons, which consist of straight-line edges, or a plurality of three-dimensional curves. Initially, the entire surface is modeled as a plurality of connected lines which represent the polygon edges or the parametric curves. The resulting model is called a line or "wireframe" model and appears as a transparent object so that the portions of the surface which lie at the back of the object as well as portions of the surface which lie at the front can be seen.
In order to make the model appear more "life-like", a viewing point is assigned and various algorithms are then used to remove "hidden" lines which represent surfaces that lie at the "back" of the model and would be obscured by surfaces which lie at the front.
Finally, in order to generate an even more lifelike shape, each of the polygonal or bicubic patches is filled in with an image or shaded with various shadings or colors. Once a three-dimensional surface has been constructed in accordance with the conventional methods and equations, it can then be subjected to transformations which involve rotation, perspective representations, translations or scaling. Normally, a transformation is performed by applying well-known transformation equations to selected points of the modeled shape called "source" points to generate "target" points which represent the source points of the shape which have been transformed to new locations.
For simple shaded surfaces, it is generally not necessary to transform each point of the surface in order to generate the transformed shape. For example, for polygonal mesh surfaces, it may be sufficient to transform the vertices of each polygon and then recalculate the shading of each surface to represent the transformed image. However, when the surfaces of the transformed model involve a pattern or image painted on each surface, then it is generally necessary to transform each single point of the graphics image to produce the transformed image as is done with the two-dimensional video special effects systems mentioned above.
The algorithms and methods for generating and transforming various 3D shapes are well-known in the art and there are many alternative choices which generate "life-like" models. Examples of conventional equations and methods can be found in various texts on computer graphics, for example, "Fundamentals of Interactive Computer Graphics" by J. D. Foley and A. Van Dam, Addison-Wesley Publishing Company, Reading, Mass., July 1984; or "Principles of Interactive Computer Graphics" by William M. Newman and Robert F. Sproull, McGraw-Hill Book Company, Second Edition, 1979.
In those cases in which each point of the modeled shape must be transformed, in all but the simplest shapes, a very large number of discrete source points must be transformed to target locations. Consequently, it is necessary to either use a large amount of specialized hardware which performs the necessary computations at a very high rate or to make the system non "real time" so that a longer time interval can be allowed to recalculate each image. In a typical computer graphics system, a compromise is made between hardware and recomputation time with the result that most images are not "real time" in that a significant delay is present between the display of separate images of a transformed object.
The speed problem becomes more complicated when "real time" video signals are displayed on each surface of the constructed three-dimensional object. Real time video signals may, for example, consist of "live" television signals and, in order for these signals to remain "live," it is necessary to transform all of the source pixels representing each surface within one field time of a typical television signal, that is, within about 16 milliseconds. Since a typical digitized television signal consists of approximately 230,000 source pixels, a large amount of specialized hardware is necessary to perform the computations necessary to transform each pixel within the required time limit.
Instead of transforming each source pixel to generate a target pixel, once a 3D surface has been constructed, it is also possible to use the computed target pixel location to locate the source pixels which generate the target pixel. When the associated source pixels have been located, the pixel value of the target pixel can be computed directly from the source pixel values. Consequently, only source pixels which actually contribute to the target pixel are used in computations. The required source pixels can be selected from each target pixel by using the inverse of the transformation equations which transform the source pixels into the target pixel. However, when even simple curved surfaces are involved, the mathematics involved in inverting the transformation matrices are extremely complex, involving equations with multiple order variables. The processing of these equations are beyond the processing speed of present day hardware for real-time video applications.
Consequently, it is an object of the present invention to provide a three-dimensional video special effects system which can operate with real-time video information.
It is another object of the present invention to provide a three-dimensional video special effects system in which real-time video information can be generated on a three-dimensional surface which surface can be manipulated while maintaining the real time video on the constructed surfaces.
It is a further object of the present invention to provide a three-dimensional video special effects system which is capable of generating three-dimensional images of a variety of surfaces including planar and curved surfaces.
It is still another object of the present invention to provide a three-dimensional video special effects system which does not require large amounts of special hardware to generate real-time video images.
It is yet another object of the present invention to provide a three-dimensional video special effects system which can achieve three-dimensional transformations in real time.
It is yet another object of the present invention to provide a three-dimensional video special effects system which is easy to use.